package array

// https://leetcode-cn.com/problems/maximum-subarray/
// 最大子序列和
// 算法：动态规划
// f[n] = max(nums[n], maxsum[n-1] + nums[n]), maxsum[n] = (nums[n] + maxsum[n-1]) >= 0 ? nums[n] + maxsum[n-1] : nums[n]
func MaxSubArray(nums []int) int {
	if 0 == len(nums) {
		return 0
	}

	maxSum := nums[0]
	currentSum := nums[0]
	// start := 0
	end := 0

	for end < len(nums)-1 {
		end++
		if currentSum >= 0 && currentSum+nums[end] >= 0 {
			currentSum += nums[end]
		} else {
			// start = end
			currentSum = nums[end]
		}
		if currentSum > maxSum {
			maxSum = currentSum
		}
	}

	return maxSum
}
